{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Garden Perimeter to Collect Enough Apples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumPerimeter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #收集足够苹果的最小花园周长"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个用无限二维网格表示的花园，<strong>每一个</strong>&nbsp;整数坐标处都有一棵苹果树。整数坐标&nbsp;<code>(i, j)</code>&nbsp;处的苹果树有 <code>|i| + |j|</code>&nbsp;个苹果。</p>\n",
    "\n",
    "<p>你将会买下正中心坐标是 <code>(0, 0)</code>&nbsp;的一块 <strong>正方形土地</strong>&nbsp;，且每条边都与两条坐标轴之一平行。</p>\n",
    "\n",
    "<p>给你一个整数&nbsp;<code>neededApples</code>&nbsp;，请你返回土地的&nbsp;<strong>最小周长</strong>&nbsp;，使得&nbsp;<strong>至少</strong>&nbsp;有<strong>&nbsp;</strong><code>neededApples</code>&nbsp;个苹果在土地&nbsp;<strong>里面或者边缘上</strong>。</p>\n",
    "\n",
    "<p><code>|x|</code>&nbsp;的值定义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>x &gt;= 0</code>&nbsp;，那么值为&nbsp;<code>x</code></li>\n",
    "\t<li>如果&nbsp;<code>x &lt;&nbsp;0</code>&nbsp;，那么值为&nbsp;<code>-x</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode-cn.com/1627790803-qcBKFw-image.png\" style=\"width: 442px; height: 449px;\" />\n",
    "<pre>\n",
    "<b>输入：</b>neededApples = 1\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>边长长度为 1 的正方形不包含任何苹果。\n",
    "但是边长为 2 的正方形包含 12 个苹果（如上图所示）。\n",
    "周长为 2 * 4 = 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>neededApples = 13\n",
    "<b>输出：</b>16\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>neededApples = 1000000000\n",
    "<b>输出：</b>5040\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= neededApples &lt;= 10<sup>15</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-garden-perimeter-to-collect-enough-apples](https://leetcode.cn/problems/minimum-garden-perimeter-to-collect-enough-apples/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-garden-perimeter-to-collect-enough-apples](https://leetcode.cn/problems/minimum-garden-perimeter-to-collect-enough-apples/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '13', '1000000000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        left, right = 1, 100001\n",
    "        while left < right:\n",
    "            mid = (left + right)>>1\n",
    "            if mid * (mid + 1) * (2 * mid + 1)<<1 < neededApples:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        while 2 * n *  (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        ans, i = 0, 0\n",
    "        while True:\n",
    "            ans += 3 * i * i\n",
    "            if ans >= neededApples:\n",
    "                return i * 4\n",
    "            i += 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        # f(i) = f(i-1) + 12 * i + 8 * (i+1 + i+2 + ... + 2*i-1) = f(i-1) + 12 * i * i\n",
    "        # f(i) = 12 * 1^2 + 12 * 2^2 + ... + 12 * i^2 = 2 * n* (n+1) * (2n+1)\n",
    "        def f(i):\n",
    "            return 2 * i * (i+1) * (2*i+1)\n",
    "\n",
    "        # f(62996) >= 10 ** 15\n",
    "        left, right = 1, 63000\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if f(mid) < neededApples:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return 8 * left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        for n in range(1,1000000):\n",
    "            area = 4 * ((n+1)**2 * n - (1+n)*n/2)\n",
    "            if area >= neededApples:\n",
    "                return 8*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def minimumPerimeter(self, neededApples: int) -> int:\n",
    "#         if not neededApples:\n",
    "#             return 0\n",
    "#         l = 3\n",
    "#         num = 12\n",
    "#         tmp = num\n",
    "#         while num < neededApples:\n",
    "#             tmp = tmp+4*l+4*(l-1)+4*(l+1)\n",
    "#             num = tmp + num\n",
    "#             l+=2\n",
    "#         return (l-1)*4\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/minimum-garden-perimeter-to-collect-enough-apples/solutions/908396/shou-ji-zu-gou-ping-guo-de-zui-xiao-hua-1rjsw/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        def f(a, n):\n",
    "            return (a + a + n - 1) * n // 2\n",
    "        x = sum = 0\n",
    "        while sum < neededApples:\n",
    "            x += 2\n",
    "            a = x // 2\n",
    "            sum += (f(a, a + 1) * 2 - a - x) * 4\n",
    "        return x * 4\n",
    "\n",
    "\n",
    "        #  6 5 4 3 4 5 6\n",
    "        #  5 4 3 2 3 4 5\n",
    "        #  4 3 2 1 2 3 4\n",
    "        #  3 2 1 0 1 2 3\n",
    "        #  4 3 2 1 2 3 4\n",
    "        #  5 4 3 2 3 4 5\n",
    "        #  6 5 4 3 4 5 6\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        l, r = 0, 10 ** 5 + 1\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if 2 * m * (m + 1) * (m * 2 + 1) >= neededApples:\n",
    "                r = m \n",
    "            else:\n",
    "                l = m \n",
    "        return r * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        # 肯定是二分，难在确定苹果的数量\n",
    "        def f(x):\n",
    "            return 4 * ((1+x) * x // 2 + (1+x) * x * x)\n",
    "        return 8 * bisect_left(range(10**15), neededApples, key=f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        # half_edge_length = 1\n",
    "        # half_edge_apple_count = 3 * half_edge_length*(half_edge_length+1)/2\n",
    "        # total_apple_count = 4*half_edge_apple_count - 4*2*half_edge_length\n",
    "\n",
    "        # while total_apple_count<neededApples:\n",
    "        #     half_edge_length += 1\n",
    "        #     half_edge_apple_count  = 3 * half_edge_length*(half_edge_length+1)/2\n",
    "        #     total_apple_count += 4*half_edge_apple_count - 4*2*half_edge_length\n",
    "        \n",
    "        # return 8*half_edge_length\n",
    "\n",
    "        n = 1\n",
    "        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        for n in range(1,1000000):\n",
    "            area = 4 * ((n+1)**2 * n - (1+n)*n/2)\n",
    "            if area >= neededApples:\n",
    "                return 8*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        x = 1\n",
    "        while True:\n",
    "            s = 4 * x * (x + 1) * (x + 1) - 2 * x * (x + 1)\n",
    "            if s >= neededApples:\n",
    "                return 8 * x\n",
    "            x += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n, total = 0, 0\n",
    "        while total < neededApples:\n",
    "            n += 1\n",
    "            total = (2*n+1)*(n+1)*n*2\n",
    "        \n",
    "        return n*8\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        left, right = 1, 100001\n",
    "        while left < right:\n",
    "            mid = (left + right)>>1\n",
    "            if 2 * mid * (mid + 1) * (2 * mid + 1) < neededApples:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        init_num = math.ceil(neededApples ** (1 / 3))\n",
    "        square = 2 * init_num * (init_num + 1) * (2 * init_num + 1)\n",
    "        while square >= neededApples:\n",
    "            init_num -= 1\n",
    "            square = 2 * init_num * (init_num + 1) * (2 * init_num + 1)\n",
    "        return 8 * (init_num + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        # f(i) = f(i-1) + 12 * i + 8 * (i+1 + i+2 + ... + 2*i-1) = f(i-1) + 12 * i * i\n",
    "        # f(i) = 12 * 1^2 + 12 * 2^2 + ... + 12 * i^2 = 2 * n* (n+1) * (2n+1)\n",
    "        def f(i):\n",
    "            return 2 * i * (i+1) * (2*i+1)\n",
    "\n",
    "        # f(62996) >= 10 ** 15\n",
    "        left, right = 1, 63000\n",
    "        while left < right:\n",
    "            mid = left + right >> 1\n",
    "            if f(mid) < neededApples:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return 8 * left\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        i=0\n",
    "        sum=0\n",
    "        while sum<neededApples:\n",
    "            i+=1\n",
    "            sum+=12*i*i\n",
    "        return i*8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        left, right, ans = 1, 100000, 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if 2 * mid * (mid + 1) * (mid * 2 + 1) >= neededApples:\n",
    "                ans = mid\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return ans * 8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = int((neededApples/4.0) ** (1/3))\n",
    "        while 2*n*(n+1)*(2*n+1) < neededApples:\n",
    "            n = n + 1\n",
    "\n",
    "        return 8*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:\n",
    "            n += 1\n",
    "        return n * 8\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\r\n",
    "        n  = 1 \r\n",
    "        total  = 0\r\n",
    "        while n:\r\n",
    "            total = 2*(2*n+1)*(n+1)*n\r\n",
    "            \r\n",
    "            if total >= neededApples:\r\n",
    "                return 8 * n\r\n",
    "            n += 1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        allApples = 0\n",
    "        n = 0\n",
    "        while allApples < neededApples:\n",
    "            n += 1\n",
    "            allApples += (12 * n * n)\n",
    "        return 8 * n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        n = 1\n",
    "        \n",
    "        def count(n):\n",
    "            total = (2*n+1)*(n+1)*n*2\n",
    "            return total\n",
    "        total = count(n)\n",
    "        while total < neededApples:\n",
    "            n += 1\n",
    "            total = count(n)\n",
    "        \n",
    "        return n*8\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        return bisect_left(range(100000), neededApples, \n",
    "            key=lambda n: 2*n*(n+1)*(n*2+1)) * 8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        left,right,ans=1,100000,0\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if 2*mid*(mid+1)*(2*mid+1) >= neededApples:\n",
    "                ans=mid\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return ans*8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        k=1\n",
    "        now=2*k*(k+1)*(2*k+1)\n",
    "        while now <neededApples:\n",
    "            k+=1\n",
    "            now=2*k*(k+1)*(2*k+1)\n",
    "        return 8*k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        sumApples = 0\n",
    "        l = 0\n",
    "\n",
    "        if neededApples <= 12:\n",
    "            return 8\n",
    "\n",
    "        while sumApples < neededApples:\n",
    "            l += 1\n",
    "            sumApples += 12 * (l ** 2)\n",
    "\n",
    "        return 8 * l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        t = 1\n",
    "        cur_total = 1 * 3 * 4\n",
    "        all_total = cur_total\n",
    "\n",
    "        while all_total < neededApples:\n",
    "            t += 1\n",
    "            cur_total = t * t * 3 * 4\n",
    "            all_total += cur_total\n",
    "        \n",
    "        return t * 2 * 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        i = floor((neededApples/4)**(1/3))\n",
    "        while 2*i*(i+1)*(i*2+1) < neededApples:\n",
    "            i += 1\n",
    "        return 8*i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        ans=0\n",
    "        cnt=0\n",
    "        while cnt<neededApples:\n",
    "            ans+=1\n",
    "            cnt+=(ans+2*ans)*(ans+1)*4-12*ans\n",
    "        return 8*ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumPerimeter(self, neededApples: int) -> int:\n",
    "        a=0\n",
    "        while True:\n",
    "            k=2*a*(a+1)*(2*a+1)\n",
    "            if k>=neededApples:return a*8\n",
    "            a+=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def minimumPerimeter(self, neededApples: int) -> int:\n",
    "    l, r = 0, int(1e5)\n",
    "    while r - l > 1:\n",
    "      n = (l + r) // 2\n",
    "      s = n * (n + 1) * (n * 2 + 1) * 2\n",
    "      if s < neededApples:\n",
    "        l = n\n",
    "      else:\n",
    "        r = n\n",
    "    return r * 8"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
